We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions.

We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden d -dimensional value w * . Every round, we are presented with a subset \mathcal{X}_t \subseteq \mathbb{R} d of possible actions. To accomplish this, we design novel cutting-plane algorithms with low "regret" -- the total distance between the true point w * and the hyperplanes the separation oracle returns. We also consider the variant where we are allowed to provide a list of several recommendations.